package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/
 * @create 2025/9/15 19:44
 * @since JDK17
 */

public class Solution46 {
    TreeNode f(TreeNode root, int s, int d) {
        if (root == null || root.val == s || root.val == d) {
            return root;
        }
        TreeNode l = f(root.left, s, d), r = f(root.right, s, d);
        if (l != null && r != null) {
            return root;
        }
        return r == null ? l : r;
    }
    boolean find(TreeNode root, int target, StringBuilder ans) {
        if (root == null || root.val == target) {
            return root != null;
        }
        ans.append('L');
        boolean l = find(root.left, target, ans);
        if (l != false) {   // 没找到
            return true;
        }
        ans.deleteCharAt(ans.length() - 1);
        ans.append('R');
        boolean r = find(root.right, target, ans);
        if (r != false) {
            return true;
        }
        ans.deleteCharAt(ans.length() - 1);
        return false;
    }

    public String getDirections(TreeNode root, int startValue, int destValue) {
        TreeNode lca = f(root, startValue, destValue);
        StringBuilder pathToStart = new StringBuilder();
        find(lca, startValue, pathToStart);
        StringBuilder pathToDest = new StringBuilder();
        find(lca, destValue, pathToDest);
        return "U".repeat(pathToStart.length()) + pathToDest.toString();
    }
}
